package test;

import com.sun.org.apache.bcel.internal.generic.SWAP;

import java.util.Arrays;

/**
 * 描述：
 *
 * @author hl
 * @date 2021/1/28 11:39
 */
public class QuickSort {
    public static void quickSort(int[] arr){
        if (arr == null || arr.length < 1) {
            return ;
        }
        sort(arr, 0, arr.length - 1);
    }

    private static void sort(int[] arr, int l, int r) {
        if (l < r) {
            int pivot = arr[(int) (l + (Math.random() * (r - l + 1)))];
            int[] p = partition(arr, l, r, pivot);
            sort(arr, l, p[0]);
            sort(arr, p[1], r);
        }
    }

    private static int[] partition(int[] arr, int l, int r, int pivot) {
        int index = l, low = l - 1, height = r + 1;
        while(index < height){
            if (arr[index] < pivot) {
                swap(arr, index, --height);
            }else if (arr[index] > pivot) {
                swap(arr, index++, ++low);
            }else{
                index++;
            }
        }
        return new int[]{low, height};
    }
    public static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {4,7,5,0};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
